package qsc.algorithm.floyd;

import java.util.Arrays;

/**
 * @auther QiuShangcheng
 * @create 2021/4/27
 */
public class Floyd {
    /**
     * Floyd算法 参考博客 https://www.cnblogs.com/skywang12345/p/3711532.html
     * <p>
     * 通过Floyd计算图G=(V,E)中各个顶点的最短路径时，需要引入一个矩阵S，矩阵S中的元素a[i][j]表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离。
     * <p>
     * 假设图G中顶点个数为N，则需要对矩阵S进行N次更新。初始时，矩阵S中顶点a[i][j]的距离为顶点i到顶点j的权值；如果i和j不相邻，则a[i][j]=∞。 接下来开始，对矩阵S进行N次更新。第1次更新时，如果"a[i][j]的距离" > "a[i][0]+a[0][j]"(a[i][0]+a[0][j]表示"i与j之间经过第1个顶点的距离")，则更新a[i][j]为"a[i][0]+a[0][j]"。 同理，第k次更新时，如果"a[i][j]的距离" > "a[i][k]+a[k][j]"，则更新a[i][j]为"a[i][k]+a[k][j]"。更新N次之后，操作完成！
     *
     * @param graph 已经初始化的图
     */
    public static void floyd(Graph graph) {
        //前置节点
        int[][] prev = new int[graph.getVertex().length][graph.getVertex().length];
        //初始化前置节点
        for (int i = 0; i < graph.getVertex().length; i++) {
            Arrays.fill(prev[i], i);
        }
        //三层for循环实现，i->k-j
        for (int k = 0; k < graph.getVertex().length; k++) {
            for (int j = 0; j < graph.getVertex().length; j++) {
                for (int i = 0; i < graph.getVertex().length; i++) {
                    int temp = graph.getMatrix()[i][k] + graph.getMatrix()[k][j];
                    if (temp < graph.getMatrix()[i][j]) {
                        graph.updateMatrix()[i][j] = temp;
                        prev[i][j] = prev[k][j];
                    }
                }
            }
        }
        //结果打印
        System.out.println("floyd->最终各个村庄最短距离:");
        for (int[] temp : graph.getMatrix()
        ) {
            System.out.println(Arrays.toString(temp));
        }
        System.out.println("前置节点矩阵为：");
        for (int[] temp : prev
        ) {
            System.out.println(Arrays.toString(temp));
        }
    }

}
